package com.example.system.class20;

/**
 * @Date 2022/8/12
 * @Author Jonathan
 */
public class Code01_Knapsack {
    public static void main(String[] args) {

    }

    public static int getMaxValue(int[] v, int[] w, int bag) {
        return process(0, 0, v, w, bag);
    }

    // 尝试函数
    public static int process(int index, int alreadyW, int[] v, int[] w, int bag) {
        if (alreadyW > bag) {
            return -1;
        }
        // 到头了 没有货了 返回0
        if (index == v.length) {
            return 0;
        }
        // 其实就是index位置要或者不要
        int p1 = process(index + 1, alreadyW, v, w, bag);
        // 上游需要知道是不是有效的
        int p2 = process(index + 1, alreadyW + w[index], v, w, bag);
        if (p2 != -1) {
            p2 += v[index];
        }
        return Math.max(p1, p2);
    }
}
